#!/usr/bin/ruby
# -*- ruby -*-
#
# http://www.reddit.com/r/dailyprogrammer/comments/1ee664/050813_challenge_124_intermediate_circular_graphs/

require 'pp'
require 'set'

g = {}

cycles = []

STDIN.readlines.each do |line|
  src, dst = line.strip.split(' ')

  next if dst.nil?

  # Get paths that terminate at the src
  to_src = g[src] || Set.new

  # Get paths that terminate at the dst
  to_dst = g[dst] || Set.new

  # For each path that terminates at the src
  to_src.each do |path|
    # Clone it
    path_clone = path.clone

    # For the cloned path, prepend the new dst
    path_clone.unshift(dst)

    # Add it to the set of paths that terminate at the dst
    to_dst << path_clone

    # If the very first node of the path is the same as the
    # destination, we have ourselves a cycle
    cycles << path_clone if path_clone.first == path_clone.last
  end

  # Add a path from src to dst that terminates at the dst
  to_dst << [dst, src]

  g[dst] = to_dst
end

pp cycles
